home *** CD-ROM | disk | FTP | other *** search
/ PC-Blue - MS DOS Public Domain Library / PC-Blue MS-DOS Public Domain Library - NYACC.iso / vol350 / prolog.arc / CAD.ARC / DREXATGS.ARC / ATGS.DOC next >
Encoding:
Text File  |  1987-04-05  |  19.3 KB  |  529 lines
  1.  
  2.                        DREXEL ATGS DOCUMENTATION  4/5/87
  3.  
  4.  
  5.                           Preliminary Documentation for 
  6.                      Drexel Automatic Test Generation System
  7.  
  8.  
  9.         I. Introduction
  10.  
  11.              Drexel  ATGS  was the result of a course project  at  Drexel 
  12.         University   involving  the  design  of  a  digital  logic   test 
  13.         generation  system  for  combinational circuits.  The  system  is 
  14.         currently  D-Algorithm  based,  and  is capable  of  providing  a 
  15.         complete,  though not minimal set of tests for any  combinational 
  16.         circuit.  New logic elements may be defined by the user. The only 
  17.         constraint is time and computer memory available. The D-algorithm 
  18.         is currently used,  but in recognition of its deficiencies may in 
  19.         the future be replaced by PODEM. A branch and bound step may also 
  20.         be added to attempt to provide a less redundant (though still not 
  21.         minimal) test set.
  22.  
  23.              Input  is  in  the  form of text files.  The  user  of  ATGS 
  24.         provides:
  25.  
  26.              1) A  netlist description.  This includes all nets  in  the 
  27.         circuit  and description is in terms of the elements which a  net 
  28.         connects.
  29.  
  30.              2)   A  gatelist  description.   The  netlist  and  gatelist 
  31.         description could be derived from each other,  but we have chosen 
  32.         to require the user to give both.
  33.              
  34.              3) A list of inputs.
  35.  
  36.              4) A list of outputs.
  37.  
  38.              5) A list of input constraints which correspond to providing 
  39.         double rail inputs.
  40.  
  41.              6) A supplemental description of whatever logic elements are 
  42.         not included in the standard ATGS library.
  43.  
  44.              
  45.              ATGS is PROLOG based,  and runnable with PD PROLOG, or other 
  46.         Edinburgh  dialect  Prologs  with  minor  modification.  ATGS  is 
  47.         supplied in the form of a Prolog source file (ATGS.PRO).  Circuit 
  48.         files are also Prolog source files. After loading, the user has a 
  49.         choice   of  activities,   which  include  generating  tests  for 
  50.         individual gates,  all inputs,  outputs,  or fanout  points.  The 
  51.         test  results  can  be  written out to a  file  with  ADA  Prolog 
  52.         versions FS and higher.
  53.  
  54.              A  sample source file provided is a circuit provided by Mark 
  55.         Karpovsky of Boston University, and is entitled "samcir.pro".
  56.  
  57.  
  58.  
  59.  
  60.  
  61.                                         1
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.                        DREXEL ATGS DOCUMENTATION  4/5/87
  69.  
  70.  
  71.         II. Writing circuit files for ATGS
  72.  
  73.              A circuit file is a Prolog language source file.  If  A.D.A. 
  74.         Prolog  is being used,  the extension (character string after the 
  75.         "." ) must be ".pro". 
  76.  
  77.              Let  us  consider the small example file  simcir.pro,  which 
  78.         contains three two input and gates.  The schematic representation 
  79.         of this file is:
  80.  
  81.                gate "o1:"
  82.                       _          gate "p1:"
  83.                n1--->| |      n5        _    
  84.                      |&|--.----------->| |   n6
  85.                n2--->|_|  |            |&|--------> (output1)
  86.                           |    /------>|_|
  87.                n3---------|---/         _
  88.                           \----------->| |   n7
  89.                             gate "p2": |&|--------> (output2)
  90.                n4--------------------->|_|
  91.  
  92.  
  93.         The   corresponding  ciruit  file  must  contain  the   following 
  94.         elements:
  95.  
  96.  
  97.         1) A list of inputs: inputs( [n1,n2,n3,n4] ).
  98.  
  99.         2) A list of outputs:  outputs( [n6,n7] ).
  100.  
  101.         3) A list of logic elements: elements( [o1,p1,p2] ).
  102.  
  103.         4) An individual descriptor for each logic element:
  104.  
  105.              o1( and2, 2, [n1,n2], n5 ).
  106.              p1( and2, 2, [n3,n5], n6 ).
  107.              p2( and2, 2, [n4,n5], n7 ).
  108.  
  109.         5) An individual netlist descriptor for each net:
  110.  
  111.              n1( 1, x1, [o1] ).
  112.              n2( 2, x2, [o1] ).
  113.              n3( 3, x3, [p1] ).
  114.              n4( 4, x4, [p2] ).
  115.              n5( 5, o1, [p1,p2] ).
  116.              n6( 6, p1, [f1] ).
  117.              n7( 7, p2, [f2] ).
  118.  
  119.         The  names by which you refer to the logic elements and nets  are 
  120.         arbitrary. Each logic descriptor has the following fields:
  121.  
  122.              a) The gate type ("and2", "or3", ...) 
  123.  
  124.              b) The second field, which is a number, is not actually used 
  125.  
  126.  
  127.                                         2
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.                        DREXEL ATGS DOCUMENTATION  4/5/87
  135.  
  136.  
  137.              by the current algorithm.
  138.  
  139.              c) A Prolog list:  [<net1>,  <net2>,...] of all the elements 
  140.              which  serve as inputs to that logic element.  The order  in 
  141.              they are given is important.  When you specify a test of the 
  142.              nth gate input gate  input,  you are actually testing the  gate 
  143.              input  which  is  connected  to the nth  net  in  the  list, 
  144.              starting with 1 and counting from the left.
  145.  
  146.         You  can also add input constraints to the system.  For  example, 
  147.         n4  might not be an externally accessible to the system,  but the 
  148.         internally generated complement of n1.  We could modify the above 
  149.         description to reflect this in the following way:
  150.  
  151.              1) Remove "n4" from the list of inputs.
  152.  
  153.              2) Add the following statement in the circuit file:
  154.  
  155.                   in1( constraint1, 1, [n1], n4 ).
  156.                 
  157.                 The  term "constraint1" refers to an inverter constraint, 
  158.                 and is defined in DREXATGS itself.
  159.  
  160.              3) Add the element "in1" to the list of circut elements:
  161.  
  162.                   elements( [o1,p1,p2,in1] ).
  163.  
  164.         The  purpose  of a constraint is to force some set of  inputs  to 
  165.         behave  in  a  particular fashion while not  actually  generating 
  166.         tests for the constraint itself.
  167.  
  168.  
  169.         III. Questions to ask ATGS
  170.  
  171.              ATGS  considers  only single stuck-at faults.  That  is,  it 
  172.         generates  tests which detect variation in circuit behavior as  a 
  173.         result  of some gate input being stuck at a either stuck-at-0  or 
  174.         stuck-at-1, which we abbreviate sa0 and sa1.
  175.  
  176.              You  can test the output of any gate in the circuit with the 
  177.         following question:
  178.  
  179.              gentestoutp( <gate name>, <fault>, <InVector>, <OutVector> ).
  180.  
  181.         Here <gate name> is o1,  p1,  and p2,  <fault> is sa0 or sa1. You 
  182.         can  name  <InVector> according to the rules which govern  Prolog 
  183.         variables.  It must begin with a capital,  and be an alphanumeric 
  184.         string.  The  same  for <OutVector>,  since it is  through  these 
  185.         variables  that the Prolog system will return the input  set  and 
  186.         ouput set which indicate the absence of the tested-for fault. 
  187.  
  188.              For example, if we give the goal:
  189.  
  190.              gentestoutp( o1, sa0, In, Out ).
  191.  
  192.  
  193.                                         3
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.                        DREXEL ATGS DOCUMENTATION  4/5/87
  201.  
  202.  
  203.  
  204.         we get:
  205.  
  206.              In = [n4(1),n2(1),n1(1)]
  207.              Out = [n7(d)].
  208.  
  209.         The meaning of the input test set should be quite obvious: we set 
  210.         these  inputs to test the circuit.  Doubtless you are  wondering: 
  211.         What  is  the meaning of n7(d),  where "d" is not  thee  expected 
  212.         Boolean  value?  The "d" is d-algorithm's way of saying that this 
  213.         output will be 1 in a correctly functioning circuit,  and 0 in  a 
  214.         circuit  which has the tested for fault.  Always,  there is  this 
  215.         equivalence:
  216.  
  217.              "d" ---> { 1 --> correct functioning, 0 --> fault }
  218.              "db"---> { 0 --> correct functioning, 1 --> fault }
  219.  
  220.              It is also possible to test for input stuck-at-faults,  with 
  221.         the goal:
  222.  
  223.              gentestinp( <gate name>, <input number>,
  224.                                  <fault>, <InVector>, <OutVector> ).
  225.  
  226.         There is one new parameter,  the input number. Recall that a gate 
  227.         description  has  a  list of inputs.  Each input  has  a  number, 
  228.         starting  from the left and beginning with one,  that corresponds 
  229.         to  the input number.  So if we wished to test the input of  gate 
  230.         "p2" which is connected to net "n4",  we would refer to the  gate 
  231.         description:
  232.  
  233.              p2( and2, 2, [n4,n5], n7 ).
  234.  
  235.         and  observe that "n4" is the first input in the list,  and  thus 
  236.         connected  to input number 1.  So to test for a sa0 fault at this 
  237.         point we would give the following goal:
  238.  
  239.              gentestinp( p2, 1, sa0, In, Out ).
  240.  
  241.                   
  242.              Suppose  we  wish to save the tests for further  processing. 
  243.         Then there are two related goals which facilitate this:
  244.  
  245.              ftinp( <gate>, <input>, <fault> )
  246.  
  247.              ftout( <gate>, <fault> )
  248.  
  249.         These goals save the test in memory as a Prolog clause, and print 
  250.         the  results to the screen as well.  Hence it is not necessary to 
  251.         give variable names for the returned results,  and there are  two 
  252.         fewer arguments. 
  253.  
  254.              If  you are using types FS or higher A.D.A.  Prolog,  it  is 
  255.         possible to write out the clauses into a disk database.  Use  the 
  256.         following invocation:
  257.  
  258.  
  259.                                         4
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.                        DREXEL ATGS DOCUMENTATION  4/5/87
  267.  
  268.  
  269.  
  270.              update( user, <testfile> ). 
  271.  
  272.         where <testfile> is a convenient file name. Give only the part of 
  273.         the  filename  before  the dot - the  system  will  automatically 
  274.         append ".pro" to it.
  275.  
  276.              You  can also erase the accumulated tests if you  wish  with 
  277.         the invocation:
  278.  
  279.              forget( user )
  280.  
  281.  
  282.         IV. Generating a Complete Set of Tests for a Circuit.
  283.  
  284.              A  complete set of tests is defined as one which will detect 
  285.         any  single stuck-at-fault anywhere in the circuit.  There is  no 
  286.         guarentee  that multiple stuck-at-faults can be  detected,  since 
  287.         one  can  mask another.  The test set generated by  ATGS  is  not 
  288.         minimal.  In  real  life,  it  is seldom possible to  generate  a 
  289.         minimal  test  set,  or it may require expenditure  of  computing 
  290.         power incommensurate with the reduction of testing cost.
  291.  
  292.              There  are  three goals in the system which  in  combination 
  293.         will  generate a complete test.  There is a theorem which  states 
  294.         that if all inputs,  outputs,  and fanout points of a circuit are 
  295.         tested for stuck-at-faults,,  then the test generated will detect 
  296.         a  single stuck-at-fault anywhere in the circuit.  A fanout point 
  297.         is simply a net which inputs to more than one gate,  and we  test 
  298.         for the driver of that net,  which is th output of some gate.  In 
  299.         the sample ciruit, there is one net with fanout: n5.
  300.  
  301.              The complete set of goals is:
  302.              
  303.              testinputs.
  304.              testoutputs.
  305.              testfanouts.
  306.  
  307.              ATGS  automatically  compiles a list of fanout  points,  and 
  308.         obtains the input and output lists from the circuit  file,  while 
  309.         ignoring the constraints.
  310.  
  311.              For   large  circuits  you  will  notice  that  runtime   is 
  312.         unpredictable,  but  tending to be largest for gates the furthest 
  313.         away from the outputs.  You may notice that ATGS does not  appear 
  314.         to  terminate  for some tests,  which simply indicates  that  the 
  315.         runtime  excessive.  These are flaws inherent in the D-algorithm. 
  316.         This field is a deep one, and there are algorithms which claim to 
  317.         be at least as good ad D-algorithm for all classes of circuits. 
  318.  
  319.              If  the algorithm appears to be incapable of finding a  test 
  320.         in  a  reasonable  time,  it is suggested that you  look  at  the 
  321.         schematic  and  decide what an equivalent test might be  that  is 
  322.         closer  to the outputs.  This is case for "samcir.pro".  For some 
  323.  
  324.  
  325.                                         5
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.                        DREXEL ATGS DOCUMENTATION  4/5/87
  333.  
  334.  
  335.         reason,  the runtime became prohibitive in finding the  following 
  336.         goal:  
  337.  
  338.              gentestoutp(  o2,  sa1,  In,  Out ).  
  339.         It  was found that by manually intervening,  it was  possible  to 
  340.         give the subtitute goal:
  341.  
  342.              gentestinp( p2, 2, sa1, In, Out ), 
  343.              (input of gate p2 from o2).
  344.  
  345.         which returned a test.
  346.  
  347.         IV. The Gate Library
  348.  
  349.         The kinds of gates which DREXATGS knows about are:
  350.  
  351.              constrainlist( [constraint1] ).
  352.  
  353.         inverter contraints:
  354.              constraint1( pc_inv, pdcfinv, pcinv ).
  355.  
  356.         noninverting buffers:
  357.              buf(  pc_buf,  pdcfbuf,  pcbuf ).
  358.  
  359.         two input and gates:
  360.              and2( pc_and2, pdcfand2, pcand2 ).
  361.  
  362.         three input and gates:
  363.              and3( pc_and3, pdcfand3, pcand3 ).
  364.  
  365.         two input or gates:
  366.              or2( pc_or2, pdcfor2, pcor2 ).
  367.  
  368.         three input or gates:
  369.              or3( pc_or3, pdcfor3, pcor3 ).
  370.  
  371.         The cubic algebra used by D-algorithm requires us to define three 
  372.         "cubes", or specialized truth tables, for each gate type:
  373.  
  374.         1.  The  primitive  cubes,  which are simply the truth tables  of 
  375.         normally operating gates:
  376.  
  377.              pc_inv( 0, [[1]] ).                                       
  378.              pc_inv( 1, [[0]] ).                                       
  379.  
  380.              pc_buf( 0, [[0]] ).                                       
  381.              pc_buf( 1, [[1]] ).                                       
  382.  
  383.              pc_and2( 0, [[0,_],[_,0]] ).                              
  384.              pc_and2( 1, [[1,1]] ).                                    
  385.  
  386.              pc_and3( 0, [[0,_,_],[_,0,_],[_,_,0]] ).                  
  387.              pc_and3( 1, [[1,1,1]] ).                                  
  388.                                                                        
  389.  
  390.  
  391.                                         6
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.                        DREXEL ATGS DOCUMENTATION  4/5/87
  399.  
  400.  
  401.              pc_or2( 1, [[1,_],[_,1]] ).                               
  402.              pc_or2( 0, [[0,0]] ).                                     
  403.  
  404.              pc_or3( 1, [[1,_,_],[_,1,_],[_,_,1]] ).                   
  405.              pc_or3( 0, [[0,0,0]] ).                                   
  406.         2.  The  primitive D-cubes of the logic elements,  which describe 
  407.         the  altered logic of a gate with a stuck-at input.  Consider the 
  408.         first statement for an inverter.  This says if an inverter has an 
  409.         input  stuck  at  0 (sa0(_)),  then if you fix  the  input  at  1  
  410.         ([[1]]) the output would be 0 in a normal circuit (db) and 1 in a 
  411.         faulty  circuit.  The  other  entries have the following  set  of 
  412.         arguments:
  413.              
  414.              a) Type of fault,  and what input where "_" means any  input 
  415.                 of the gate.
  416.  
  417.              b) The relation of the output to the fault, where "d" means
  418.                 normally 1 and "db" means normally 0
  419.                        
  420.              c) The input set which is required to produce faulty output,
  421.                 enclosed in double brackets.
  422.  
  423.              pdcfinv(  sa0(_), db, [[1]] ).                            
  424.              pdcfinv(  sa1(_), d,  [[0]] ).                            
  425.  
  426.              pdcfbuf(  sa0(_), d,  [[1]] ).                            
  427.              pdcfbuf(  sa1(_), db, [[0]] ).                            
  428.  
  429.              pdcfand2( sa0(_), d,  [[1,1]] ).                          
  430.              pdcfand2( sa1(1), db, [[0,1]] ).                          
  431.              pdcfand2( sa1(2), db, [[1,0]] ).                          
  432.  
  433.              pdcfand3( sa0(_), d,  [[1,1,1]] ).                        
  434.              pdcfand3( sa1(1), db, [[0,1,1]] ).                        
  435.              pdcfand3( sa1(2), db, [[1,0,1]] ).                        
  436.              pdcfand3( sa1(3), db, [[1,1,0]] ).                        
  437.                                                                        
  438.              pdcfor2( sa0(1), d, [[1,0]] ).                            
  439.              pdcfor2( sa0(2), d, [[0,1]] ).                            
  440.              pdcfor2( sa1(_), db, [[0,0]] ).                           
  441.                                                                        
  442.              pdcfor3( sa0(1), d, [[1,0,0]] ).                          
  443.              pdcfor3( sa0(2), d, [[0,1,0]] ).                          
  444.              pdcfor3( sa0(3), d, [[0,0,1]] ).                          
  445.              pdcfor3( sa1(_), db, [[0,0,0]] ).                         
  446.                                                                        
  447.         3)  The  propagation D-cubes of the elements.  The essence of  D-
  448.         algorithm  is to cause a fault to matter at the gate under  test, 
  449.         and propagate it to the outputs so that it becomes observable. To 
  450.         do  this,  we must define how a gate transmit faults presented at 
  451.         its inputs.
  452.  
  453.  
  454.              /* The propagation D-cubes of the logic elements: */      
  455.  
  456.  
  457.                                         7
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.                        DREXEL ATGS DOCUMENTATION  4/5/87
  465.  
  466.  
  467.                                                                        
  468.              pcinv( d,  [[db]] ).                                      
  469.              pcinv( db, [[d]] ).                                      
  470.              pcbuf( d, [[d]] ).                                        
  471.              pcbuf( db, [[db]] ).                                      
  472.              pcand2( d, [[1,d],[d,1],[d,d]] ).                         
  473.              pcand2( db,[[1,db],[db,1],[db,db]] ).                     
  474.              pcor2( d, [[0,d],[d,0,],[d,d]] ).                         
  475.              pcor2( db, [[0,db],[db,0],[db,db]] ).                     
  476.              pcand3( d, [[d,1,1],[1,d,1],[1,1,d],                      
  477.                   [d,d,1],[d,1,d],[1,d,d],[d,d,d]] ).                  
  478.              pcand3( db, [[db,1,1],[1,db,1],[1,1,db],[db,db,1],        
  479.                         [db,1,db],[1,db,db],[db,db,db]] ).             
  480.              pcor3( d, [[d,0,0],[0,d,0],[0,0,d],                       
  481.                        [d,d,0],[d,0,d],[0,d,d],[d,d,d]] ).             
  482.              pcor3( db, [[db,0,0],[0,db,0],[0,0,db],                   
  483.                        [db,db,0],[db,0,db],[0,db,db],[db,db,db]] ).    
  484.  
  485.         From  these examples,  you should be able to construct the  three 
  486.         cubic  types  (primitive,  D,  and  propagation)  for  any  logic 
  487.         subblocks you wish to include in a circuit.  For more information 
  488.         on  D-algorithm  I refer you to the  excellent,  though  somewhat 
  489.         dated book by Brewer and Friedman, Diagnosis & Reliable Design of 
  490.         Digital  Systems,   1976,   by  the  Computer  Science  Press  of 
  491.         Rockville, MD.
  492.  
  493.  
  494.                                    Bob Morein
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506.  
  507.  
  508.  
  509.  
  510.  
  511.  
  512.  
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.                                         8
  524.  
  525.  
  526.  
  527.  
  528.  
  529.